home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / cpp_libs / awe2-0_1.lha / awe2-0.1 / Src / RCS / GenericHeap.cc,v < prev    next >
Text File  |  1989-02-20  |  7KB  |  363 lines
  1. head     3.2;
  2. branch   ;
  3. access   ;
  4. symbols  ;
  5. locks    ; strict;
  6. comment  @@;
  7.  
  8.  
  9. 3.2
  10. date     89.02.20.15.34.45;  author grunwald;  state Exp;
  11. branches ;
  12. next     3.1;
  13.  
  14. 3.1
  15. date     88.12.20.13.48.47;  author grunwald;  state Exp;
  16. branches ;
  17. next     1.2;
  18.  
  19. 1.2
  20. date     88.10.30.13.03.07;  author grunwald;  state Exp;
  21. branches ;
  22. next     1.1;
  23.  
  24. 1.1
  25. date     88.09.18.16.42.22;  author grunwald;  state Exp;
  26. branches ;
  27. next     ;
  28.  
  29.  
  30. desc
  31. @@
  32.  
  33.  
  34. 3.2
  35. log
  36. @Start using Gnu library heaps for schedulers
  37. @
  38. text
  39. @// This may look like C code, but it is really -*- C++ -*-
  40. // 
  41. // Copyright (C) 1988 University of Illinois, Urbana, Illinois
  42. //
  43. // written by Dirk Grunwald (grunwald@@cs.uiuc.edu)
  44. //
  45. #include "Awesime.h"
  46. #include "stream.h"
  47. //
  48. //    This defines a Pairing Heap structure for a pointer data type.
  49. //
  50. //    See ``The Pairing Heap: A New Form of Self-Adjusting Heap''
  51. //    Fredman, Segdewick et al,
  52. //    Algorithmica (1986) 1:111-129
  53. //
  54. //    In particular, this implements the pairing heap using the circular
  55. //    list.
  56. //
  57. //
  58.  
  59. #ifndef HEAP_INDEX
  60. #define HEAP_INDEX unsigned short
  61. #endif
  62.  
  63. #ifndef HEAP_INDEX_NULL
  64. #define HEAP_INDEX_NULL 0xffff
  65. #endif
  66.  
  67. #define NIL    GENERIC2(HEAP_NAME,Null)
  68. #define INDEX    GENERIC2(HEAP_NAME,Index)
  69. #define ITEM    GENERIC2(HEAP_NAME,Item)
  70. #define RECORD    GENERIC2(HEAP_NAME,Record)
  71.  
  72. const INDEX NIL = HEAP_INDEX_NULL;
  73. static const char *GENERIC2(HEAP_NAME,Name) = GENERIC_STRING(HEAP_NAME) ;
  74.  
  75. HEAP_NAME::HEAP_NAME(int length, bool xdebug)
  76.     : (xdebug)
  77. {
  78.     freelist = NIL;
  79.     allocatedSize = 0;
  80.     root = NIL;
  81.     elements = 0;
  82.     makeRoom(length);
  83. }
  84.  
  85. INDEX HEAP_NAME::getCell()
  86. {
  87.     if (freelist == NIL) {
  88.     makeRoom(0);
  89.     }
  90.     INDEX cell = freelist;
  91.     pValid[freelist] = 1;
  92.     freelist = storage[freelist].sibling;
  93.     elements++;
  94.     return(cell);
  95. }
  96.  
  97. void
  98. HEAP_NAME::returnCell(INDEX cell)
  99. { 
  100.     storage[cell].sibling = freelist;
  101.     pValid[cell] = 0;
  102.     freelist = cell;
  103.     elements--;
  104. }
  105.  
  106. void
  107. HEAP_NAME::makeRoom(int atLeast)
  108. {
  109.     //
  110.     //    Out of free space?
  111.     //
  112.     if (freelist == NIL) {
  113.     //
  114.     // Is there existing storage?
  115.     //
  116.     if (allocatedSize > 0) {
  117.         //
  118.         // Get new storage, copy over existing data & delete old storage
  119.         // 
  120.         INDEX newSize = (allocatedSize * 3) / 2;
  121.  
  122.         RECORD *newStorage = new RECORD[newSize];
  123.         char *newValid = new char[newSize];
  124.         if (newStorage == 0 || newValid == 0) {
  125.         cerr << "[" << GENERIC2(HEAP_NAME,Name) << "::makeRoom] Out of storage space\n";
  126.         exit(1);
  127.         }
  128.         bcopy(storage, newStorage, allocatedSize * sizeof(RECORD));
  129.         bcopy(pValid, newValid, allocatedSize * sizeof(char));
  130.         delete storage;
  131.         delete pValid;
  132.         storage = newStorage;
  133.         pValid = newValid;
  134.         //
  135.         // Chain the new stuff into the free list
  136.         //
  137.         for (int i = allocatedSize; i < newSize; i++) {
  138.         storage[i].sibling = i+1;
  139.         pValid[i] = 0;
  140.         }
  141.         storage[newSize-1].sibling = NIL;
  142.         freelist = allocatedSize;
  143.         allocatedSize = newSize;
  144.     } else {
  145.         //
  146.         // No existing space
  147.         //
  148.         if (atLeast <= 8) {
  149.         allocatedSize = 8;
  150.         } else {
  151.         allocatedSize = atLeast;
  152.         }
  153.         storage = new RECORD[allocatedSize];
  154.         pValid = new char[allocatedSize];
  155.         if (storage == 0) {
  156.         cerr << "[" << GENERIC2(HEAP_NAME,Name) << "::getCell] Out of storage\n";
  157.         exit(1);
  158.         }
  159.         for (int i = 0; i < allocatedSize; i++) {
  160.         storage[i].sibling = i+1;
  161.         pValid[i] = 0;
  162.         }
  163.         storage[allocatedSize-1].sibling = NIL;
  164.         freelist = 0;
  165.     }
  166.     }
  167. }
  168.  
  169. //
  170. // makeChild takes two nodes and makes one the child of the other
  171. // and returns the index of the new parent. 
  172. //
  173. // We play fast and loose with the siblings field of a & b, although
  174. // we maintain the siblings of the children.
  175. //
  176. INDEX
  177. HEAP_NAME::makeChild(INDEX a, INDEX b)
  178. {
  179.     INDEX parent;
  180.     INDEX child;
  181.     
  182.     if (storage[a].item <= storage[b].item) {
  183.     parent = a; child = b;
  184.     } else {
  185.     parent = b; child = a;
  186.     }
  187.     //
  188.     // If the new parent has no children, simply add the new child.
  189.     // We assume that the child and the parent dont care about
  190.     // their *sibling* nodes
  191.     //
  192.     INDEX popsKid = storage[parent].children;
  193.     
  194.     if (popsKid == NIL) {
  195.     storage[parent].children = child;
  196.     storage[child].sibling = child;
  197.     } else {
  198.     INDEX temp = storage[popsKid].sibling;
  199.     storage[popsKid].sibling = child;
  200.     storage[child].sibling = temp;
  201.     storage[parent].children = child;
  202.     }
  203.     return(parent);
  204. }
  205.  
  206. void
  207. HEAP_NAME::add(ITEM &item)
  208. {
  209.     INDEX cell = getCell();
  210.  
  211.     storage[cell].item = item;
  212.     storage[cell].children = NIL;
  213.     storage[cell].sibling = NIL;
  214.     
  215.     if (root == NIL) {
  216.     root = cell;
  217.     } else {
  218.      //
  219.     //    Make cell a child of root. Root may have no kids.
  220.     //
  221.     root = makeChild(root,cell);
  222.     }
  223. }
  224.  
  225. //
  226. //    Item remove is the most complicated routine.
  227. //
  228. //    We remove the root (should there be one) and then select a new
  229. //    root. The siblings of the root are in a cicular list. We continue
  230. //    to pair elements in this list until there is a single element.
  231. //    This element will be the new root.
  232. bool
  233. HEAP_NAME::remove(ITEM &removed)
  234. {
  235.     bool valid = FALSE;
  236.     
  237.     do {
  238.     if (root == NIL || elements <= 0) {
  239.         return(0);
  240.     }
  241.     
  242.     removed = storage[root].item;
  243.     valid = pValid[root];
  244.     
  245.     INDEX child = storage[root].children;
  246.     returnCell(root);
  247.     
  248.     if (child == NIL) {
  249.         root = NIL;
  250.     } else {
  251.         while(storage[child].sibling != child) {
  252.         //
  253.         // We have at least two kids, but we may only have
  254.         // two kids. So, oneChild != child, but it is possible
  255.         // that twoChild == child.
  256.         //
  257.         INDEX oneChild = storage[child].sibling;
  258.         INDEX twoChild = storage[oneChild].sibling;
  259.         //
  260.         // Remove the two from the sibling list
  261.         //
  262.         storage[child].sibling = storage[twoChild].sibling;
  263.         storage[oneChild].sibling = NIL;
  264.         storage[twoChild].sibling = NIL;
  265.         
  266.         INDEX bestChild = makeChild(oneChild, twoChild);
  267.         
  268.         if (twoChild == child) {
  269.             //
  270.             // We have reduced the two to one, so we'll be exiting.
  271.             //
  272.             child = bestChild;
  273.             storage[child].sibling = child;
  274.         } else {
  275.             //
  276.             // We've removed two siblings, now we need to insert
  277.             // the better of the two
  278.             //
  279.             storage[bestChild].sibling = storage[child].sibling;
  280.             storage[child].sibling = bestChild;
  281.             child = storage[bestChild].sibling;
  282.         }
  283.         }
  284.         root = child;
  285.     }
  286.     } while ( !valid );
  287.     return(1);
  288. }
  289.  
  290. bool
  291. HEAP_NAME::doStart(INDEX &index)
  292. {
  293.     for (index = 0; index < allocatedSize; index++) {
  294.     if (pValid[index]) {
  295.         return(TRUE);
  296.     }
  297.     }
  298.     return(FALSE);
  299. }
  300.  
  301. bool
  302. HEAP_NAME::doDelete(INDEX &index)
  303. {
  304.     if (pValid[index]) {
  305.     pValid[index] = FALSE;
  306.     elements--;
  307.     return(TRUE);
  308.     } else {
  309.     return( FALSE );
  310.     }
  311. }
  312.  
  313. bool
  314. HEAP_NAME::doNext(INDEX& index)
  315. {
  316.     //
  317.     // If they are moving on to the next element,
  318.     // they are sitting on the current on. So, move to the next
  319.     // and then look for a valid one.
  320.     //
  321.     for (index++; index < allocatedSize; index++) {
  322.     if (pValid[index]) {
  323.         return(TRUE);
  324.     }
  325.     }
  326.     return(FALSE);
  327. }
  328.  
  329. void
  330. HEAP_NAME::doDone()
  331. {
  332.     //
  333.     // Do nothing.
  334.     //
  335. }
  336.  
  337. @
  338.  
  339.  
  340. 3.1
  341. log
  342. @Steay version
  343. @
  344. text
  345. @@
  346.  
  347.  
  348. 1.2
  349. log
  350. @*** empty log message ***
  351. @
  352. text
  353. @@
  354.  
  355.  
  356. 1.1
  357. log
  358. @Initial revision
  359. @
  360. text
  361. @d1 6
  362. @
  363.